package listbyorder.access001_100.test37;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/5/31 8:54
 */
public class Solution1 {

    // 方法一： 300斩回溯
    public void solveSudoku(char[][] board) {
        dfs(board);
    }

    private boolean dfs(char[][] board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') {
                    char count = '1';
                    while (count <= '9') {
                        if (isVilid(board, count, i, j)) {
                            board[i][j] = count;
                            if (dfs(board)) {
                                return true;
                            } else {
                                board[i][j] = '.';
                            }
                        }
                        count++;
                    }
                    return false;
                }
            }
        }
        return true;
    }

    private boolean isVilid(char[][] board, char count, int i, int j) {
        for (int k = 0; k < 9; k++) {
            if (board[i][k] == count) {
                return false;
            }
        }

        for (int k = 0; k < 9; k++) {
            if (board[k][j] == count) {
                return false;
            }
        }

        int s_r = (i / 3) * 3;
        int s_c = (j / 3) * 3;
        for (int k = s_r; k < s_r + 3; k++) {
            for (int l = s_c; l < s_c + 3; l++) {
                if (board[k][l] == count) {
                    return false;
                }
            }
        }

        return true;
    }
}
